package _回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// 131 ： 分割回文串 ：https://leetcode.cn/problems/palindrome-partitioning/description/
// 回溯，没有优化的版本
// 切割型回溯算法
public class _131_分割回文串 {

    List<List<String>> res = new ArrayList<>();
    List<String> path = new ArrayList<>();

    public List<List<String>> partition(String s) {
        back(s, 0);
        return res;
    }

    private void back(String s, int start) {
        if (start >= s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start + 1; i <= s.length(); i++) {
            if (isPalindrome(s, start, i - 1)) {
                String str = s.substring(start, i); // [ , )左闭右开的区间
                path.add(str);
                back(s, i);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r))
                return false;
            l++;
            r--;
        }
        return true;
    }

    // 132：分割成回文串的最小次数 https://leetcode.cn/problems/palindrome-partitioning-ii/description/
    public int minCut(String s) {
        char[] chars = s.toCharArray();
        int len = s.length();
        // 提前计算是否回文
        boolean[][] isPalindrome = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            Arrays.fill(isPalindrome[i], true);
        }

        for (int y = len - 1; y >= 0; y--) {
            for (int x = y + 1; x < len; x++) {
                isPalindrome[y][x] = (s.charAt(y) == s.charAt(x)) && (isPalindrome[y + 1][x - 1]);
            }
        }
        // dp[i] 表示 s[0:i] 的最小分割次数
        int[] dp = new int[len];
        // dp[i] = min(dp[j-1] + 1) if s[j:i] 是回文串
        for (int i = 0; i < len; i++) {
            dp[i] = i;
            for (int j = 0; j <= i; j++) {
                if (isPalindrome[j][i]) {
                    dp[i] = j == 0 ? 0 : Math.min(dp[i], dp[j - 1] + 1);
                }
            }
        }
        return dp[len - 1];
    }

}
